//栈 - 删除字符串中的所有相邻重复项
//方法一: 使用STL栈
class Solution {
public:
    string removeDuplicates(string s) {
        stack<int> st;
        for(int i = 0; i < s.size(); i++)
        {
            if(st.size() && s[i] == st.top()) st.pop(); 
            else st.push(s[i]);
        }
        string ret;
        while(!st.empty())
        {
            ret.push_back(st.top());
            st.pop(); 
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};


//方法二: string模拟栈
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for(auto ch : s)
        {
            if(ret.size() && ret.back() == ch) ret.pop_back();
            else ret += ch;
        }
        return ret;
    }
};